package dp.路径;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 不同路径ii63.java
 * @createTime 2024年02月29日 17:39:00
 */
public class 不同路径ii63 {
	/*
   状态和选择：位置，路线
   dp函数：定义dp函数dp(i，j)表示达到位置i,j的方案数量为dp[i][j]
   如果i和j有障碍物，那么就是
   转移方程：
   dp[i][j]=dp[i][j-1]+dp[i-1][j]
   baseCase:
   1. 有障碍物的边方案为0，没有障碍物的边方案为1
   2. 两条边：如果i存在障碍物，那么dp[i][0]后面的都为0,如果j未存在障碍物那么[0][j]后面的为0
   边界：
	障碍物如果在开始和结尾，为0
	*/
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		if (obstacleGrid[0][0] == 1) {
			return 0;
		}
		int row = obstacleGrid.length;
		int col = obstacleGrid[0].length;
		if (obstacleGrid[row - 1][col - 1] == 1) {
			return 0;
		}
		int[][] dp = new int[row][col];

		boolean hasObstacle = false;
		for (int i = 0; i < row; i++) {
			if (hasObstacle) {
				dp[i][0] = 0;
				continue;
			}
			if (obstacleGrid[i][0] == 1) {
				dp[i][0] = 0;
				hasObstacle = true;
			} else {
				dp[i][0] = 1;
			}
		}
		hasObstacle = false;
		for (int j = 0; j < col; j++) {
			if (hasObstacle) {
				dp[0][j] = 0;
				continue;
			}
			if (obstacleGrid[0][j] == 1) {
				dp[0][j] = 0;
				hasObstacle = true;
			} else {
				dp[0][j] = 1;
			}
		}

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (obstacleGrid[i][j] == 1) {
					dp[i][j] = 0;
				} else {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
		}
		return dp[row - 1][col - 1];
	}
}
